import java.util.Arrays;

class Solution {

    // 判断出现的字符是否唯一
    public boolean isUnique1(String astr) {
        // 哈希表记录遍历的字符
        int[] hash = new int[26];
        for (int i = 0; i < astr.length(); i++) {
            char ch = astr.charAt(i);
            if (hash[ch-'a'] != 0) {
                // 说明已经出现了重复的字符
                return false;
            } else {
                hash[ch-'a']++;
            }
        }
        return true;
    }

    public boolean isUnique(String astr) { // 位图版
        int ret = 0;
        int n = astr.length();
        if (n > 26) { // 多于26个，那么肯定是有重复的了
            return false;
        }
        for (int i = 0; i < n; i++) {
            int temp = astr.charAt(i)-'a';
            if ((ret & (1<<temp)) != 0) { // 重复了
                return false;
            } else {
                ret |= (1<<temp);
            }
        }
        return true;
    }


    // 丢失的数字
    public int missingNumber1(int[] nums) {
        // 哈希表遍历统计
        int n = nums.length;
        int[] hash = new int[n+1];
        for (int i = 0; i < n; i++) {
            hash[nums[i]]++;
        }
        for (int i = 0; i < n+1; i++) {
            if (hash[i] == 0) { // 找到了
                return i;
            }
        }
        return -1;
    }

    public int missingNumber2(int[] nums) {
        // 找出最大值
        int n = nums.length;
        Arrays.sort(nums); // 排序
        if (n != nums[n-1]) {
            return n;
        }
        for (int i = 0; i < n; i++) {
            if (i != nums[i]) {
                return i;
            }
        }
        return -1;
    }

    public int missingNumber3(int[] nums) {
        // 遍历求和
        int sum1 = 0;
        int n = nums.length;
        for (int i = 0; i < n+1; i++) {
            sum1 += i;
        }
        for (int i = 0; i < n; i++) {
            sum1 -= nums[i];
        }
        return sum1;
    }

    public int missingNumber(int[] nums) {
        int sum1 = 0;
        int n = nums.length;
        for (int i = 0; i < n+1; i++) {
            sum1 ^= i;
        }
        for (int i = 0; i < n; i++) {
            sum1 ^= nums[i];
        }
        return sum1;
    }

    public static void main(String[] args) {
        Thread t = new Thread(new Runnable() {
            @Override
            public void run() {
                System.out.println("1");
            }
        });
        t.start();
        System.out.println("2");
    }

}